﻿// 3681. 小镇购物.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*

https://www.acwing.com/problem/content/3684/

CSU 镇上有 n 个商店，n个商店由 m条双向小路相连。

在这 n个商店里共有 k种不同商品，商品编号为 1∼k，每个商店只有一种商品。

每条小路的权重都为 1，也就是说一个人走过一条小路所需的代价为 1。

请问，从每个商店出发，派出足够多的人前往各个商店购物，买够 k种商品中的 s 种商品所需的最小代价。

不考虑人员折返，可派遣的人员数量无限，初始商店所售商品也计入 s 种商品以内。

输入格式
输入包含多组测试数据。

每组数据第一行包含四个整数 n,m,k,s。

第二行包含 n个整数 a1,a2,…,an
，表示每个商店的所售商品种类。

接下来 m行，每行包含两个整数 u,v
，表示商店 u 和 v之间存在一条小路。

输出格式
每组数据输出一行 n 个整数，其中第 i 个数表示从第 i 个商店出发，买够 s 种商品所需的最小代价。

数据范围
1≤n≤104
,
1≤m≤105
,
1≤s≤k≤min(n,100)
,
1≤ai≤k
,
1≤u,v≤n
,
u≠v
,
每个测试点均保证所有 n相加之和不超过 104。

输入样例：
5 5 4 3
1 2 4 3 2
1 2
2 3
3 4
4 1
4 5
7 6 3 2
1 2 3 3 2 2 1
1 2
2 3
3 4
2 5
5 6
6 7
输出样例：
2 2 2 2 3
1 1 1 2 2 1 1
*/
int main()
{
    std::cout << "Hello World!\n";
}
 